package 力扣_数学思维题;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**914.卡牌分组
 * @author zx
 * @create 2022-04-24 10:15
 */
public class Num914 {
    /**
     * 方法一：gcd
     避免一个误区，相同数字不一定放在同一组。可以分开。但是要遵守X的规则
     自己第一次做这个题就陷入了这个误区,可以参考第一次提交,而gcd()避免了这个误区
     */
    public boolean hasGroupsSizeX(int[] deck) {
        int n = deck.length;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < n;i++){
            if(map.containsKey(deck[i])){
                map.put(deck[i],map.get(deck[i]) + 1);
            }else{
                map.put(deck[i],1);
            }
        }
        List<Integer> values = new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            values.add(entry.getValue());
        }
        int number = -1;
        for(int i = 0;i < values.size();i++){
            if(number == -1){
                number = values.get(i);
            }else{
                number = gcd(number,values.get(i));
            }
        }
        return number >= 2;
    }
    public int gcd(int a,int b){
        return b == 0 ? a : gcd(b,a % b);
    }

    /**
     * @return 暴力枚举
     */
    public boolean hasGroupsSizeX2(int[] deck) {
        int n = deck.length;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < n;i++){
            if(map.containsKey(deck[i])){
                map.put(deck[i],map.get(deck[i]) + 1);
            }else{
                map.put(deck[i],1);
            }
        }
        List<Integer> values = new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            values.add(entry.getValue());
        }
        for(int x = 2;x <= n;x++){
            if(n % x == 0){
                boolean flag = true;
                for(int i = 0;i < values.size();i++){
                    if(values.get(i) % x != 0){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    return true;
                }
            }
        }
        return false;
    }
}
